﻿public class Solution {
    public void SolveSudoku(char[][] board)
    {
        Trackbacking(board, 0, 0);
    }

    /// <summary>
    /// 填充数独中的一格
    /// </summary>
    /// <param name="board">数独</param>
    /// <param name="row">当前填充的行号</param>
    /// <param name="cul">当前填充的列号</param>
    private bool Trackbacking(char[][] board, int row, int cul)
    {
        // 寻找合适插入点
        bool flag = false;
        for (; row < board.Length; row++)
        {
            for (int c = 0; c < board[row].Length; c++)
            {
                if (board[row][c] == '.')
                {
                    flag = true;
                    cul = c;
                    break;
                }
            }
            if (flag) break;
        }
        
        // 找到了合适的插入点
        if (flag)
        {
            // 依次填充1-9
            for (int i = 1; i < 10; i++)
            {
                if (IsValid(board, row, cul, i))
                {
                    board[row][cul] = (char)(i + '0');
                    if (Trackbacking(board, row, cul)) return true;
                    board[row][cul] = '.';
                }
            }
            return false;
        }
        return true;
    }
    
    // 判断特定位置是否可以填充num
    private bool IsValid(char[][] board, int row, int cul, int num)
    {
        char c = (char)('0' + num);
        // 遍历行
        for (int i = 0; i < board[row].Length; i++)
        {
            if (c == board[row][i]) return false;
        }
        
        // 遍历列
        for (int i = 0; i < board.Length; i++)
        {
            if (c == board[i][cul]) return false;
        }
        
        // 遍历9宫格
        int startRow = (row / 3) * 3;
        int startCol = (cul / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++)
        {
            for (int j = startCol; j < startCol + 3; j++)
            {
                if (c == board[i][j]) return false;
            }
        }
        return true;
    }

    public static void Main(string[] args)
    {
        char[][] board = new char[][]
        {
            new char[] { '5', '3', '.', '.', '7', '.', '.', '.', '.' },
            new char[] { '6', '.', '.', '1', '9', '5', '.', '.', '.' },
            new char[] { '.', '9', '8', '.', '.', '.', '.', '6', '.' },
            new char[] { '8', '.', '.', '.', '6', '.', '.', '.', '3' },
            new char[] { '4', '.', '.', '8', '.', '3', '.', '.', '1' },
            new char[] { '7', '.', '.', '.', '2', '.', '.', '.', '6' },
            new char[] { '.', '6', '.', '.', '.', '.', '2', '8', '.' },
            new char[] { '.', '.', '.', '4', '1', '9', '.', '.', '5' },
            new char[] { '.', '.', '.', '.', '8', '.', '.', '7', '9' }
        };

        Solution solution = new Solution();
        solution.SolveSudoku(board);

        for (int i = 0; i < board.Length; i++)
        {
            for (int j = 0; j < board[i].Length; j++)
            {
                Console.Write($"{board[i][j]} ");
            }
            Console.WriteLine();
        }
    }
}